#pragma once


template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t ans = 0;
		for (auto ch : s)
		{
			ans += ch;
			ans *= 31;
		}
		return ans;
	}
};


namespace openaddress
{
	enum Stat
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Stat _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(size);
			_n = 0;
		}

		Data* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key
					&& _tables[hashi]._state == EXIST)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable<K, V> newTables(_tables.size() * 2);
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
						newTables.Insert(_tables[i]._kv);
				}
				_tables.swap(newTables._tables);
			}
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		bool Erase(const K& key)
		{
			auto ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<Data> _tables;
		size_t _n;
	};

}

namespace hashbucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable(size_t size = 10)
		{
			_tables.resize(10, nullptr);
			_n = 0;
		}
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					Node* curr = _tables[i];
					while (curr)
					{
						Node* next = curr->_next;
						delete curr;
						curr = next;
					}
				}
				_tables[i] = nullptr;
			}
		}
		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			if (_tables[hashi])
			{
				Node* curr = _tables[hashi];
				while (curr)
				{
					if (curr->_kv.first == key)
						return curr;
					curr = curr->_next;
				}
			}
			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			Hash hs;
			if (_n == _tables.size())
			{
				vector<Node*> newTables(_tables.size() * 2, nullptr);
				for (auto e : _tables)
				{
					if (e)
					{
						Node* curr = e;
						while (curr)
						{
							Node* next = curr->_next;
							size_t hashi = hs(curr->_kv.first) % newTables.size();

							curr->_next = newTables[hashi];
							newTables[hashi] = curr;

							curr = next;
						}
						e = nullptr;
					}
				}
				_tables.swap(newTables);
			}

			size_t hashi = hs(kv.first) % _tables.size();
			Node* newnode = new Node(kv);

			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			auto ret = Find(key);
			if (ret)
			{
				Node* curr = _tables[hashi];
				if (curr->_kv.first == key)
				{
					_tables[hashi] = curr->_next;
					delete curr;
				}
				else
				{
					while (curr->_next->_kv.first != key)
						curr = curr->_next;
					Node* del = curr->_next;
					curr->_next = del->_next;
					delete del;
				}
				return  true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<Node*> _tables;
		size_t _n;
	};
}